This invention relates to a maximum a posteriori probability (MAP) decoding method and to a decoding apparatus that employs this decoding method. More particularly, the invention relates to a maximum a posteriori probability decoding method and apparatus for calculating backward probability and then calculating forward probability in maximum a posteriori probability decoding, thereby reducing amount of memory used.
Error correction codes, which are for the purpose of correcting errors contained in received information or in reconstructed information so that the original information can be decoded correctly, are applied to a variety of systems. For example, error correction codes are applied in cases where data is to be transmitted without error when performing mobile communication, FAX or other data communication, and in cases where data is to be reconstructed without error from a large-capacity storage medium such as a magnetic disk or CD.
Among the available error correction codes, it has been decided to adopt turbo codes (see the specification of U.S. Pat. No. 5,446,747) for standardization in next-generation mobile communications. Maximum a posteriori probability decoding (MAP decoding) manifests its effectiveness in such turbo codes. A MAP decoding method is a method of decoding that resembles Viterbi decoding.
(a) Viterbi Decoding
Using a kth item of data of encoded data obtained by encoding information of information length N, Viterbi decoding selects, for each state prevailing at the moment of input of the kth item of data, whichever of two paths that lead to the state has the smaller error, discards the path having the larger error, thenceforth, and is similar fashion, selects, for each state prevailing at the moment of input of a final Nth item of data, whichever of two paths that lead to the state has the smaller error, and performs decoding using the paths of smallest error among the paths selected at each of the states. The result of decoding is a hard-decision output.
Since the Viterbi decoding method is a method of decoding convolutional codes, convolutional encoding will be described first and then Viterbi decoding will be described.
FIG. 11 shows an example of a convolutional encoder, which has a 2-bit shift register SFR and two exclusive-OR gates EXOR1, EXOR2. The EXOR1 outputs the exclusive-OR g0 between an input and R1, and the EXOR2 outputs the exclusive-OR g1 (outputs xe2x80x9c1xe2x80x9d when xe2x80x9c1xe2x80x9d is odd and outputs xe2x80x9c0xe2x80x9d otherwise) between the input and R0, R1. Accordingly, the relationship between the input and outputs of the convolutional encoder and the states of the shift register SFR in an instance where the input data is 01101 are as illustrated in FIG. 12.
The content of the shift register SFR of the convolutional encoder is defined as the xe2x80x9cstatexe2x80x9d. As shown in FIG. 13, there are four states, namely 00, 01, 10 and 11, which are referred to as state a, state b, state c and state d, respectively. With the convolutional encoder of FIG. 11, the outputs (g0,g1) and the next state are uniquely defined depending upon which of the states a through d is indicated by the state of the shift register SFR and depending upon whether the next item of input data is xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d. FIG. 14 is a diagram showing the relationship between the states of the convolutional encoder and the inputs and outputs thereof, in which the dashed lines indicate a xe2x80x9c0xe2x80x9d input and the solid lines a xe2x80x9c1xe2x80x9d input.
(1) If xe2x80x9c0xe2x80x9d is input in state a, the output is 00 and the state is a; if xe2x80x9c1xe2x80x9d is input, the output is 11 and the state becomes c.
(2) If xe2x80x9c0xe2x80x9d is input in state b, the output is 11 and the state is a; if xe2x80x9c1xe2x80x9d is input, the output is 00 and the state becomes c.
(3) If xe2x80x9c0xe2x80x9d is input in state c, the output is 01 and the state becomes b; if xe2x80x9c1xe2x80x9d is input, the output is 10 and the state becomes d.
(4) If xe2x80x9c0xe2x80x9d is input in state d, the output is 10 and the state becomes b; if xe2x80x9c1xe2x80x9d is input, the output is 01 and the state becomes d.
If the convolutional codes of the convolutional encoder shown in FIG. 11 are expressed in the form of a lattice using the above input/output relationship, the result is as shown in FIG. 15(a), where k signifies the time at which a kth bit is input and the initial (k=0) state of the encoder is a(00). The dashed line indicates a xe2x80x9c0xe2x80x9d input and the solid line a xe2x80x9c1xe2x80x9d input, and the two numerical values on the lines are the outputs (g0, g1). Accordingly, it will be understood that if xe2x80x9c0xe2x80x9d is input in the initial state a(00), the output is 00 and the state is state a, and that if xe2x80x9c1xe2x80x9d is input, the output is 11 and the state becomes state c.
Upon referring to this lattice-like representation, it will be understood that if the original data is 11001, state c is reached via the path indicated by the dashes arrows in FIG. 15(b), and that the outputs of the encoder become
11xe2x86x9210xe2x86x9210xe2x86x9211xe2x86x9211
When a convolutional code is decoded, first a decision concerning the received data is rendered. There are two types of decisions, namely a hard decision and a soft decision.
In the case of a hard decision, the decision is rendered on the basis of two quantization levels, i.e., xe2x80x9c1xe2x80x9d is decided if the detected output level is larger than 0 and xe2x80x9c0xe2x80x9d is decided if the detected output level is less than 0. If a standardized determination is made is this fashion, an erroneous decision occurs at the spreading portion (the portion indicated by the hatched area) of the skirts of the respective probability density functions shown in FIG. 16.
A soft decision compensates for this disadvantage of the hard decision. The detected output is quantized at eight levels, as indicated by one example on the left side of FIG. 16, likelihood weighting conforming to each level is applied and the results of the decisions are output to a decoder.
With Viterbi decoding, a hard-decision input and a hard-decision output as well as a soft-decision input and a hard-decision output are possible. The former will be described first.
If the ideal error-free state is assumed, in which the hard-decision receive data (g0,g1) is 11xe2x86x9210xe2x86x9210xe2x86x9211xe2x86x9211, a path indicated by the dashed arrows shown in FIG. 17(a) is obtained. By making the dashed lines xe2x80x9c0xe2x80x9ds and the solid lines xe2x80x9c1xe2x80x9ds, the decoded result 11001 can be obtained, as illustrated in FIG. 17(b). In actuality, however, there are many cases where the receive data contains an error. If the fifth bit develops an error so that the hard-decision receive data (g0,g1) is 11xe2x86x9210xe2x86x9200xe2x86x9211xe2x86x9211, confusion occurs at time k=2 as to whether to branch to 10 or 01 (error count ERR=1). If 10 is construed to be the state and the upper path is selected, state c is reached without confusion at k=3 and k=4. Accordingly, the error count becomes error count ERR=1 on the dashed-arrow path and the decoded result at this time becomes 11001. On the other hand, if 01 is construed to be the state and the lower path is selected at time k=2, then confusion occurs at time k=3 also as to where to branch and total error count ERR=2 is the result. Thereafter, and in similar fashion, paths are selected and, when branching confusion occurs, ERR is counted up. The following results are eventually obtained:
total error count ERR when decoded result is 11001: 1
total error count ERR when decoded result is 11100: 2
total error count ERR when decoded result is 11110: 3
total error count ERR when decoded result is 11111: 3
Accordingly, the decoded result 11001 for which the error count ERR is smallest is selected and output. If this arrangement is adopted, the original data 11001 can be detected correctly even if the receive data is erroneous.
Though the foregoing relates to hard-decision receive data, decoding can be executed in similar fashion in the case of soft-decision receive data as well. FIG. 18 is a diagram useful in describing decoding in the case of soft-decision receive data. Assume that the soft-decision receive data (g0,g1) is 1,1xe2x86x921,0xe2x86x921,0xe2x86x922/8,1xe2x86x921,1, as indicated at (b). Referring to the lattice-type representation shown at (a), it will be appreciated that confusion occurs at time k=3 as to whether to branch to 11 or 00. If 11 is construed to be the state and the upper path is selected (error count ERR=6/8), state c is reached without confusion at k=4. Accordingly, the error count becomes error count ERR=6/8 on the dashed-arrow path and the decoded result at this time becomes 11001. On the other hand, if 00 is construed to be the state and the lower path is selected at time k=3 (error count ERR=1+2/8), then confusion occurs at time k=4 also as to where to branch and total error count ERR=(2+2/8) is the result. Thereafter, and in similar fashion, paths are selected and, when branching confusion occurs, ERR is counted up. The following results are eventually obtained:
total error count ERR when decoded result is 11001:6/8
total error count ERR when decoded result is 11010:2+2/8
total error count ERR when decoded result is 11011:2+2/8
Accordingly, the decoded result 11001 for which the error count ERR is smallest is selected and output. If this arrangement is adopted, the original data 11001 can be detected correctly even if the receive data is erroneous. Thus, the soft decision is the same as the hard decision; the error count just is no longer an integer.
Processing for thus obtaining the error counts ERR of all possible paths based upon the receive data and decoding the original data from the path for which the error count is smallest is complicated. Accordingly, Viterbi decoding is performed as set forth below. It will be assumed that the receive data is 111000 as the result of a hard decision. At state a where k=3 in FIG. 18, there are two input paths. If only the relevant paths are extracted and drawn, the result is as shown in FIG. 19(a). The two paths are path (1) and path (2) shown in the drawing. If the hamming distances between the receive data and the decoded data obtained on respective ones of the paths are calculated, the results will be 3 and 4, as illustrated in FIGS. 19(b), (c).
On the basis of the results of calculation, the hamming distance for which the assumption is xe2x80x9cstate a reached by traversing path (1)xe2x80x9d is shorter than that for which the assumption is xe2x80x9cstate a reached by traversing path (2)xe2x80x9d. Accordingly, since the fact that the data was transmitted on path (1) has a high degree of reliability, this path is left as a survivor and the other path is discarded. If this processing for adopting or rejecting paths is executed successively with regard to each of the states a to d starting from time k=1, it is possible to find the paths for which the hamming distances to each of the states a, b, c, d at any time k are shortest (the paths of minimum error). Similar adopt-or-reject processing can continue from this point onward.
When N-items of receive data have been input, the path for which the error is smallest is decided from among the four paths of minimum error leading to respective ones of the states a, b, c, d at k=N and the decoded data is output based upon this path. FIG. 20 illustrates the shortest paths leading to respective ones of the states a to d at each time k when the receive data is 1110001111. The numerical values on the lines are the hamming distances. Accordingly, since the path leading to state c is that for which the error is smallest, the decoded data will be 11001 if decoding is performed in accordance with this path.
This decoding algorithm is referred to as xe2x80x9cmaximum likelihood decodingxe2x80x9d, in which the most likely items are selected. It is referred to also as the Viterbi algorithm because it started with Viterbi.
(b) Overview of MAP Decoding
With Viterbi decoding, the paths of large error at discarded at each state and these paths are not at all reflected in the decision regarding paths of minimum error. Unlike Viterbi decoding, MAP decoding is such that even a path of large error at each state is reflected in the decision regarding paths of minimum error, whereby decoded data of higher precision is obtained. The states a to d will be expressed by a state m (=0 to 3) below.
(b-1) First Feature of MAP Decoding
With MAP decoding, the probabilities xcex10,k(m), xcex11,k(m) that decoded data uK is xe2x80x9c0xe2x80x9d, xe2x80x9c1xe2x80x9d in each state (m=0, 1, 2, 3) at time k are decided based upon {circle around (1)} probabilities xcex10,kxe2x88x921(m), xcex11,kxe2x88x921(m) in each state at time (kxe2x88x921), {circle around (2)} the trellis (whether or not a path exists) between states at time (kxe2x88x921) and time k, and {circle around (3)} receive data ya, yb at time k. The probabilities xcex10,kxe2x88x921(m), xcex11,kxe2x88x921(m) are referred to as xe2x80x9cforward probabilitiesxe2x80x9d. Further, the probability found by taking the trellis {circle around (2)} and receive data {circle around (3)} into account, namely the probability of a shift from state mxe2x80x2 (=0 to 3) at time (kxe2x88x921) to state m (=0 to 3) at time k is referred to as the xe2x80x9cshift probabilityxe2x80x9d.
(b-2) Second Feature of MAP Decoding
With Viterbi decoding, the path of minimum error leading to each state at a certain time k is obtained taking into account the receive data from 1 to k and the possible paths from 1 to k. However, the receive data from k to N and the paths from k to N are not at all reflected in the decision regarding paths of minimum error. Unlike Viterbi decoding, MAP decoding is such that receive data from k to N and paths from k to N are reflected in decoding processing to obtain decoded data of higher precision.
More specifically, the probability xcex2k(m) that a path of minimum error will pass through each state m (=0 to 3) at time k is found taking into consideration the receive data and trellises from N to k. Then, by multiplying the probability xcex2k(m) by the forward probabilities xcex10,k(m), xcex11,k(m) of the corresponding state, a more precise probability that the decoded data uK in each state m (m=0, 1, 2, 3) at time k will become xe2x80x9c0xe2x80x9d, xe2x80x9c1xe2x80x9d is obtained.
To this end, the probability xcex2k(m) in each state m (m=0, 1, 2, 3) at time k is decided based upon {circle around (1)} the probability xcex2k+1(m) in each state at time (k+1), {circle around (2)} the trellis between states at time (k+1) and time k, and {circle around (3)} receive data ya, yb at time (k+1). The probability xcex2k(m) is referred to as xe2x80x9cbackward probabilityxe2x80x9d. Further, the probability found by taking the trellis {circle around (2)} and receive data {circle around (3)} into account, namely the probability of a shift from state mxe2x80x2 (=0 to 3) at time (k+1) to state m (=0 to 3) at time k is the shift probability.
Thus, the MAP decoding method is as follows, as illustrated in FIG. 21:
(1) Letting N represent information length, the forward probabilities xcex10,k(m), xcex11,k(m) of each state (m=0 to 3) at time k are calculated taking into consideration the encoded data of 1 to k and trellises of 1 to k. That is, the forward probabilities xcex10,k(m), xcex11,k(m) of each state are found from the probabilities xcex10,kxe2x88x921(m), xcex11,kxe2x88x921(m) and shift probability of each state at time (kxe2x88x921).
(2) Further, the backward probability xcex2k(m) of each state (m=0 to 3) at time k is calculated using the receive data of N to k and the paths of N to k. That is, the backward probability xcex2k(m) of each state is calculated using the backward probability xcex2k+1(m) and shift probability of each state at time (k+1).
(3) Next, the forward probabilities and backward probability of each state at time k are multiplied to obtain the joint probabilities as follows:
xcex0,k(m)=xcex10,k(m)xc2x7xcex2k(m),
xe2x80x83xcex1,k(m)=xcex11,k(m)xc2x7xcex2k(m)
(4) This is followed by finding the sum total xcexa3mxcex0,k(m) of the probabilities of xe2x80x9c0xe2x80x9d and the sum total xcexa3mxcex1,k(m) of the probabilities of xe2x80x9c1xe2x80x9d in each state, calculating the probability that the original data uk of the kth item of data is xe2x80x9c1xe2x80x9d and the probability that the data uk is xe2x80x9c0xe2x80x9d based upon the magnitudes of the sum totals, outputting the larger probability as the kth item of decoded data and outputting the likelihood. The decoded result is a soft-decision output.
(c) First MAP Decoding Method According to Prior Art
(c-1) Overall Structure of MAP Decoder
FIG. 22 is a block diagram of a MAP decoder for implementing a first MAP decoding method according to the prior art. Encoding route R, information length N, original information u, encoded data xa, xb and receive data ya, yb are as follows:
That is, encoded data xa, xb is generated from the original information u of information length N, an error is inserted into the encoded data at the time of reception, data ya, yb is received and the original information u is decoded from the receive data.
Upon receiving (yak,ybk) at time k, the shift-probability calculation unit 1 calculates the following probabilities and saves them in a memory 2:
probability xcex30,k that (xak,xbk) is (0,0)
probability xcex31,k that (xak,xbk) is (0,1)
probability xcex32,k that (xak,xbk) is (1,0)
probability xcex33,k that (xak,xbk) is (1,1)
Using the forward probability xcex11,kxe2x88x921(m) that the original data ukxe2x88x921 is xe2x80x9c1xe2x80x9d and the forward probability xcex10,kxe2x88x921(m) that the original data uk is xe2x80x9c0xe2x80x9d in each state m (=0 to 1) at the immediately preceding time (kxe2x88x921), as well as the obtained shift probabilities xcex30,k, xcex31,k, xcex32,k, xcex33,k at time k, a forward-probability calculation unit 3 calculates the forward probability xcex11,k(m) that the original data uk is xe2x80x9c1xe2x80x9d and the forward probability xcex10,kxe2x88x921(m) that the original data uk is xe2x80x9c0xe2x80x9d at time k and stores these probabilities in memories 4a to 4d. It should be noted that since processing always starts from state m=0, the initial values of forward probabilities are xcex10,0(0)=xcex11,0(0)=1, xcex10,0(m)=xcex11,0(m)=0 (where mxe2x89xa00).
The shift-probability calculation unit 1 and forward-probability calculation unit 3 repeat the above-described calculations at k=k+1, perform the calculations from k=1 to k=N to calculate the shift probabilities xcex30,k, xcex31,k, xcex32,k, xcex33,k and forward probabilities xcex11,k, xcex10,k at each of the times k=1 to N and store these probabilities in memory 2 and memories 4a to 4d, respectively.
Thereafter, a backward-probability calculation unit 5 calculates the backward probability xcex2k(m) (m=0 to 3) in each state m (=0 to 3) at time k using the backward probability xcex2k+1 and shift probability xcex3s,k+1 (s=0, 1, 2, 3) at time (k+1), where it is assumed that the initial value of k is Nxe2x88x921 that the trellis end state is m=0 and that xcex2N(0)=1, xcex2N(1)=xcex2N(2)=xcex2N(3)=0 hold.
A first arithmetic unit 6a in a joint-probability calculation unit 6 multiplies the forward probability xcex11,k(m) and backward probability xcex2k(m) in each state m (=0 to 3) at time k to calculate the probability xcex1,k(m) that the kth item of original data uk is xe2x80x9c1xe2x80x9d, and a second arithmetic unit 6b in the joint-probability calculation unit 6 uses the forward probability xcex10,k(m) and backward probability xcex2k(m) in each state m (=0 to 3) at time k to calculate the probability xcex0,k(m) that the kth item of original data uk is xe2x80x9c0xe2x80x9d.
A uk and uk likelihood calculation unit 7 adds the xe2x80x9c1xe2x80x9d probabilities xcex1,k(m) (m=0 to 3) in each of the states m (=0 to 3) at time k, adds the xe2x80x9c0xe2x80x9d probabilities xcex0,k(m) (m=0 to 3) in each of the states m (=0 to 3), decides the xe2x80x9c1xe2x80x9d, xe2x80x9c0xe2x80x9d of the kth item of data uk based upon the results of addition, namely the magnitudes of xcexa3mxcex1,k(m) and xcexa3mxcex0,k(m), calculates the confidence (likelihood) L(uk) thereof and outputs the same.
The backward-probability calculation unit 5, joint-probability calculation unit 6 and uk and uk likelihood calculation unit 7 subsequently repeat the foregoing calculations at k=k+1, perform the calculations from k=N to k=1 to decide the xe2x80x9c1xe2x80x9d, xe2x80x9c0xe2x80x9d of the original data uk at each of the times k=1 to N, calculate the confidence (likelihood) L(uk) thereof and output the same.
(c-2) Calculation of Forward Probabilities
The forward probability xcex1ik(m) that the decoded data uk will be i (xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d) is obtained in accordance with the following equation based upon {circle around (1)} forward probability xcex1ikxe2x88x921(m) in each state at time (kxe2x88x921) and {circle around (2)} transition probability xcex3i(Rk,mxe2x80x2,m) of a transition from state mxe2x80x2 (=0 to 3) at time (kxe2x88x921) to state m (=0 to 3) at time k:
xcex1ik(m)=xcexa3mxe2x80x2xcexa3jxcex3i(Rk,mxe2x80x2,m)xc2x7xcex1ikxe2x88x921(mxe2x80x2)/xcexa3mxcexa3mxe2x80x2xcexa3ixcexa3jxcex3i(Rk,mxe2x80x2,m)xc2x7xcex1ikxe2x88x921(mxe2x80x2)xe2x80x83xe2x80x83(1)
Here the transition probability xcex3i(Rk,mxe2x80x2,m) is found based upon the trellis between state mxe2x80x2 (=0 to 3) at time (kxe2x88x921) and the state m (=0 to 3) at time k as well as the receive data ya, yb at time k. Since the denominator in the above equation is a portion eliminated by division in the calculation of uk and likelihood of uk, it need not be calculated. If the forward probabilities xcex10k(0), xcex11k(0) that the original data uk will be xe2x80x9c0xe2x80x9d, xe2x80x9c1xe2x80x9d in state m=0 at time k in the above equation are represented diagrammatically, the result will be as shown in FIG. 23.
If it is assumed that a convolutional encoder is constructed by connecting two flip-flops FF1, FF2 and three exclusive-OR gates EXOR1 to EXOR3 in the manner illustrated, the flip-flops FF1, FF2 take on four states m (=0 to 3) of (00), (10), (01), (11). If xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d is input at each state, the relationship between the input/output data and the states before and after will be as shown in FIG. 25. In FIG. 25, the left side indicates state mxe2x80x2 at time kxe2x88x921, the right side indicates the state m at time k after a kth item of data is input, the solid lines the paths of the state transition when xe2x80x9c0xe2x80x9d is input and the dashed lines the paths of the state transition when xe2x80x9c1xe2x80x9d is input, and 00, 11, 10, 01 on the paths indicate the values of the output signals xa, xb. By way of example, if xe2x80x9c0xe2x80x9d is input in the state mxe2x80x2=1, the output is 01 and the state becomes m=3; if xe2x80x9c1xe2x80x9d is input, the output is 10 and the state becomes m=2.
The transition probability xcex3i(Rk,mxe2x80x2,m) is the probability of a transition from the state mxe2x80x2 (=0 to 3) at time (kxe2x88x921) when the input data is i (xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d) to the state m (=0 to 3) at time k. This is found in accordance with the following equation:
xcex3i(Rk,mxe2x80x2,m)=pxc2x7qxc2x7xcfx80xe2x80x83xe2x80x83(2)
where p is a value related to the receive data. However q, xcfx80 are constant values decided by whether or not there is a transition path (trellis) from state mxe2x80x2 at time (kxe2x88x921) to state m at time k. The result is shown in FIG. 26. If there is no transition path, then
qxc2x7xcfx80=0
holds. Thus, it will suffice to calculate only p in the transition probabilities xcex30(Rk,0,0) and xcex31(Rk,2,0) marked by o in FIG. 26; everything else becomes zero. If the lines of transition probabilities of zero in FIG. 23 are eliminated, therefore, the forward probabilities xcex10k(0), xcex11k(0) that uk is xe2x80x9c0xe2x80x9d, xe2x80x9c1xe2x80x9d will be as shown in FIG. 27. That is, the forward probabilities are found from the following:
xcex10k(0)=xcex30(Rk,0,0)xc2x7xcex10kxe2x88x921(0)+xcex30(Rk,0,0)xc2x7xcex11kxe2x88x921(0)xe2x80x83xe2x80x83(3)
xcex11k(0)=xcex31(Rk,2,0)xc2x7xcex10kxe2x88x921(2)+xcex31(Rk,2,0)xc2x7xcex11kxe2x88x921(2)xe2x80x83xe2x80x83(4)
Transition probabilities are related to the trellises between states and to the receive data. Found from the transition probabilities are {circle around (1)} shift probability xcex30,k that (xak, xbk) is (0,0) {circle around (2)} shift probability xcex31,k that (xak, xbk) is (0,1), ( shift probability xcex32,k that (xak, xbk) is (1,0) and ( shift probability xcex33,k that (xak, xbk) is (1,1). For example, Equation (3) obtains xcex10k(0) via the transition path of (xak, xbk)=(0,0). We therefore have
transition probability xcex30(Rk,0,0)=shift probability xcex30,k 
Further, Equation (4) obtains xcex11k(0) via the transition path of (xak, xbk)=(0,0). We therefore have
transition probability xcex31(Rk,2,0)=shift probability xcex33,k 
Accordingly, Equations (3), (4) become as follows:
xcex10k(0)=xcex30,kxc2x7xcex10kxe2x88x921(0)+xcex30,kxc2x7xcex11kxe2x88x921(0)xe2x80x83xe2x80x83(3)xe2x80x2
xcex11k(0)=xcex33,kxc2x7xcex10kxe2x88x921(2)+xcex33,kxc2x7xcex11kxe2x88x921(2)xe2x80x83xe2x80x83(4)xe2x80x2
Similarly, xcex10k(m), xcex11k(m) of m=1 to 3 are found.
(c-3) Calculation of Backward Probability
The backward probability xcex2k(m) of each state is obtained in accordance with the following equation based upon {circle around (1)} backward probability xcex2k+1(m) in each state at time (k+1) and {circle around (2)} transition probability xcex3i(Rk+1,mxe2x80x2,m) of a transition from state m (=0 to 3) at time k to state mxe2x80x2 (=0 to 3) at time (k+1):
xcex2k(m)=xcexa3mxe2x80x2xcexa3ixcex3i(Rk+1,m,mxe2x80x2)xc2x7xcex2k+1(mxe2x80x2)/xcexa3mxcexa3mxe2x80x2xcexa3ixcexa3jxcex3i(Rk,m,mxe2x80x2)xc2x7xcex1ik(m)xe2x80x83xe2x80x83(5)
Here the transition probability xcex3i(Rk+1,m,mxe2x80x2) is found based upon the trellis between state m (=0 to 3) at time k and the state mxe2x80x2 (=0 to 3) at time (k+1) as well as the receive data ya, yb at time (k+1). Since the denominator in the above equation is a portion eliminated by division in the calculation of likelihood, it need not be calculated.
If xcex2k(0) in state m=0 at time k in the above equation is represented diagrammatically, the result will be as shown in FIG. 28. If a transition path does not exist, then qxc2x7xcfx80=0 holds, as mentioned above. Accordingly, it will suffice to calculate only p in the transition probabilities xcex30(Rk+1,0,0) and xcex31(Rk+1,0,1) marked; everything else becomes zero. If the lines of the transition probability of zero in FIG. 28 are eliminated, therefore, the backward probability xcex2k(0) will be as shown in FIG. 29. That is, the backward probability is found from the following:
xe2x80x83xcex2k(0)=xcex30(Rk+1,0,0)xc2x7xcex2k+1(0)+xcex31(Rk+1,0,1)xc2x7xcex2k+1(1)xe2x80x83xe2x80x83(6)
Transition probabilities are related to the trellises between states and receive data. Found from the transition probabilities are {circle around (1)} transition
probability xcex30,k+1 that (xak+1, xbk+1) is (0,0), {circle around (2)} transition
probability xcex31,k+1 that (xak+1, xbk+1) is (0,1), {circle around (3)} transition
probability xcex32,k+1 that (xak+1, xbk+1) is (1,0) and
{circle around (4)} transition probability xcex33,k+1 that (xak+1, xbk+1) is (1,1).
For example, the first term on the right side of Equation (6) obtains xcex2k(0) via the transition path of (xak+1, xbk+1)=(0,0). We therefore have
transition probability xcex30(Rk+1,0,0)=shift probability xcex30,k+1 
Further, the second term on the right side of Equation (6) obtains xcex2k(0) via the transition path of (xak+1, xbk+1) =(1,1). We therefore have
transition probability xcex31(Rk+1,0,1)=shift probability xcex33,k+1 
Accordingly, Equation (6) becomes as follows:
xcex2k(0)=xcex30,k+1xc2x7xcex2k+1(0)+xcex33,k+1xc2x7xcex2k+1(1)xe2x80x83xe2x80x83(6)xe2x80x2
Similarly, xcex2k(1), xcex2k(2), xcex2k(3) of m=1 to 3 can be found.
(c-4) Calculation of Joint Probabilities and Likelihood
FIG. 30 is a diagram useful in describing calculation of joint probabilities, uk and likelihood of uk.
If the forward probabilities xcex10,k(m), xcex11,k(m) and backward probability xcex2k(m) of each state at time k are found, these are multiplied to calculate the joint probabilities as follows:
xcex0k(m)=xcex10k(m)xc2x7xcex2k(m)
xcex1k(m)=xcex11k(m)xc2x7xcex2k(m)
The sum total xcexa3mxcex0k(m) of the probabilities of xe2x80x9c0xe2x80x9d and the sum total xcexa3mxcex1k(m) of the probabilities of xe2x80x9c1xe2x80x9d in each of the states are then obtained and the likelihood is output in accordance with the following equation:
L(u)=log [xcexa3mxcex1k(m)/xcexa3mxcex0k(m)]xe2x80x83xe2x80x83(7)
Further, the decoded result uk=1 is output if L(u) greater than 0 holds and the decoded result uk=0 is output if L(u) less than 0 holds. That is, the probability that the kth item of original data uk is xe2x80x9c1xe2x80x9d and the probability that it is xe2x80x9c0xe2x80x9d are calculated based upon the magnitudes of the sum total xcexa3mxcex0k(m) of the probabilities of xe2x80x9c0xe2x80x9d and of the sum total xcexa3mxcex1k(m) of the probabilities of xe2x80x9c1xe2x80x9d, and the larger probability is output as the kth item of decoded data.
(c-5) Problem With First MAP Decoding Method
The problem with the first MAP decoding method of the prior art shown in FIG. 22 is that the memory used is very large. Specifically, the first MAP decoding method requires a memory of 4xc3x97N for storing transition probabilities and a memory of m (number of states)xc3x972xc3x97N for storing forward probabilities, for a total memory of (4+mxc3x972)xc3x97N. Since actual calculation is accompanied by soft-decision signals, additional memory which is eight times this figure is required. For example, if signal length N=5120 bits holds, number of states m=4 holds in case of constraint length=3 and number of soft-decision quantization bits=8 holds, then the required amount of memory is
(4+4xc3x972)xc3x975120xc3x978=491.52 kilobits
(c-6) Modification
The memory 2 for storing shift probabilities is not necessarily required, and an arrangement can be adopted in which the backward probability xcex2k(m) is calculated by calculating the shift probability xcex3s,k+1 (s=0, 1, 2, 3) as necessary. FIG. 31 is a modification of a MAP decoder for implementing the first MAP decoding method from which memory 2 has been removed. According to this modification, the amount of memory required is
(4xc3x972)xc3x975120xc3x978=327.7 kilobits
(d) Second MAP Decoding Method According to Prior Art
Accordingly, in order to reduce memory, a method considered is to perform the calculations upon switching the order in which the forward probability and backward probability are calculated. FIG. 32 is a block diagram of a MAP decoder for implementing this second MAP decoding method. Components identical with those shown in FIG. 22 are designated by like reference characters. An input/output reverser 8, which suitably reverses the order in which receive data is output, has a memory for storing all receive data and a data output unit for outputting the receive data in an order that is the reverse of or the same as that in which the data was input. With a turbo decoder that adopts the MAP decoding method as its decoding method, it is necessary to interleave the receive data and therefore the decoder has a memory for storing all receive data. This means that this memory for interleaving can also be used as the memory of the input/output reverser 8. Hence there is no burden associated with memory.
The shift-probability calculation unit 1 uses receive data (yak,ybk) at time k (=N), calculates the following probabilities and saves them in the memory 2:
probability xcex30,k that (xak,xbk) is (0,0)
probability xcex31,k that (xak,xbk) is (0,1)
probability xcex32,k that (xak,xbk) is (1,0)
probability xcex33,k that (xak,xbk) is (1,1)
The backward-probability calculation unit 5 calculates the backward probability xcex2kxe2x88x921(m) (m=0 to 3) in each state m (=0 to 3) at time kxe2x88x921 using the backward probability xcex2k(m) and shift probability xcex3s,k (s=0, 1, 2, 3) at time k (=N) and stores the backward probabilities in memory 9.
The shift-probability calculation unit 1 and forward-probability calculation unit 3 subsequently repeat the above-described calculations at k=k+1, perform the calculations from k=N to k=1 to calculate the shift probabilities xcex30,k, xcex31,k, xcex32,k, xcex33,k and backward probability xcex2k(m) at each of the times k=1 to N and store these probabilities in memories 2, 9.
Thereafter, using the forward probability xcex11,kxe2x88x921(m) that the original data ukxe2x88x921 is xe2x80x9c1xe2x80x9d and the forward probability xcex10,kxe2x88x921(m) that the original data ukxe2x88x921 is xe2x80x9c0xe2x80x9d at time (kxe2x88x921), as well as the obtained shift probabilities xcex30,k, xcex31,k, xcex32,k, xcex33,k at time k, the forward-probability calculation unit 3 calculates the forward probability xcex11,k(m) that uk is xe2x80x9c1xe2x80x9d and the forward probability xcex10,k(m) that uk is xe2x80x9c0xe2x80x9d in each state m (=0 to 3) at time k. It should be noted that the initial value of k is 1.
The joint-probability calculation unit 6 multiplies the forward probability xcex11,k(m) and backward probability xcex2k(m) in each state m 0 to 3 at time k to calculate the probability xcex1,k(m) that the kth item of original data uk is xe2x80x9c1xe2x80x9d, and similarly uses the forward probability xcex10,k(m) and backward probability xcex2k(m) in each state 0 to 3 at time k to calculate the probability xcex0,k(m) that the original data uk is xe2x80x9c0xe2x80x9d.
The uk and uk likelihood calculation unit 7 adds the xe2x80x9c1xe2x80x9d probabilities xcex1,k(m) (m=0 to 3) of each of the states 0 to 3 at time k, adds the xe2x80x9c0xe2x80x9d probabilities xcex0,k(m) (m=0 to 3) of each of the states 0 to 3 at time k, decides the xe2x80x9c1xe2x80x9d, xe2x80x9c0xe2x80x9d of the kth item of data uk based upon the results of addition, namely the magnitudes of xcexa3mxcex11,k(m) and xcexa3mxcex10,k(m), calculates the confidence (likelihood) L(uk) thereof and outputs the same.
The forward-probability calculation unit 3, joint-probability calculation unit 6 and uk and uk likelihood calculation unit 7 subsequently repeat the foregoing calculations at k=k+1, perform the calculations from k=1 to k=N to decide the xe2x80x9c1xe2x80x9d, xe2x80x9c0xe2x80x9d of uk at each of the times k=1 to N, calculate the confidence (likelihood) L(uk) thereof and output the same.
In accordance with the second MAP decoding method, as shown in the time chart of FIG. 33, the processing for calculation of shift probability, for calculation of backward probability and for storing the results of calculation in memory is executed in the first half, and the processing for calculation forward probability, for calculation of joint probability and for computation of original data and likelihood is executed in the second half. In other words, with the second MAP decoding method, forward probabilities xcex11,k(m), xcex10,k(m) are not stored but the backward probability xcex2k(m) is stored. As a result, memory required for the second MAP decoding method is just 4xc3x97N for storing shift probability and number of states mxc3x97N for storing backward probability, so that the total amount of memory required is (4+m)xc3x97N. Thus the amount of memory required can be reduced in comparison with the first MAP decoding method. The reduction ratio xcex7 is
xcex7=(4+m)/(4+mxc3x972)
In a case where the number m of states is small (number of states m=4 holds if constraint length=3 holds), the reduction ratio is
xcex7=(4+4)/(4+4xc3x972)=69.2%
so that memory can be reduced by about 30%. Further, if the number m of states is large, we have
xcex7≈m/(mxc3x972)=50%
The memory 2 for storing shift probabilities is not necessarily required, and an arrangement can be adopted in which the forward probabilities xcex11,k(m), xcex10,k(m) are calculated by calculating the shift probability xcex3s,k (s=0, 1, 2, 3) on each occasion. FIG. 34 shows a modification of a MAP decoder for implementing the second MAP decoding method from which the memory 2 has been removed. According to this modification, the total memory required is (mxc3x97N). Thus the amount of memory required can be reduced in comparison with the modification of the first MAP decoding method shown in FIG. 31. The reduction ratio xcex7 is
xcex7=mxc3x97N/(mxc3x972)xc3x97N=50%
(e) Third MAP Decoding Method
In accordance with the second MAP decoding method, memory used can be reduced in comparison with the first MAP decoding method. However, there is still room for a further reduction.
FIG. 35(a) is a diagram useful in describing the operation sequence of the third MAP decoding method, which makes possible a further reduction in memory used. This represents a further expansion of the second MAP decoding method. In FIG. 35, the operation sequence of the second MAP decoding method is indicated at (b) for the purpose of contrasting the second and third MAP decoding methods. The third MAP decoding method is a method disclosed in IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATION, VOL. 16, NO. 2, FEBRUARY 1998, xe2x80x9cAn Intuitive Justification and a Simplified Implementation of the MAP Decoder for Convolutional Codesxe2x80x9d, Andrew J. Viterbi.
In FIG. 35, the B operation signifies backward probability calculation/shift probability calculation, the A operation signifies forward probability calculation/shift probability calculation, and the L operation signifies joint probability calculation/likelihood calculation. With the second MAP decoding method, as indicated at (b), (1) the B operation is performed in its entirety and the results are stored in memory from N to 1, then (2) uk and likelihood (uk) are output while performing the A operation and the L operation successively from 1 to N. According to the second MAP decoding method, however, Nxc3x97m of memory is required in order to store the backward probability xcex2k(m).
Accordingly, in the third MAP decoding method, k=1 to N is divided equally into segments M and MAP decoding is executed as set forth below.
First, (1) the B operation is performed from k=2M to k=0. In the B operation, the backward probability xcex2k(m) is not calculated from k=N; calculation starts from an intermediate position k=2M. As a consequence, the backward probability xcex2k(m) found over k=2M to k=M in the first half cannot be trusted and is discarded. The backward probability xcex2k(m) found over k=M to k=1 in the second half can be trusted and therefore this is stored in memory. (2) Next, the A operation is performed at k=0, the L operation is performed using the results xcex11,1(m), xcex10,1(m) of the A operation at k=1 and xcex21(m) that has been stored in memory, and the decoded result u1 and likelihood L (ui) are calculated based upon the joint probabilities. Thereafter, and in similar fashion, the A operation is performed from k=2 to k=M and the L operation is performed based upon the results of the A operation and the results of the B operation in memory. This ends the calculation of the decoded result uk and likelihood L (uk) from k=1 to k=M.
Next, (3) the B operation is performed from k=3M to M+1. In the B operation, the backward probability xcex2k(m) is not calculated from k=N; calculation starts from an intermediate position k=3M. As a consequence, the backward probability xcex2k(m) found over k=3M to k=2M+1 in the first half cannot be trusted and is discarded. The backward probability xcex2k(m) found over k=2M to k=M+1 in the second half can be trusted and therefore this is stored in memory. (4) Next, the A operation is performed at k=M+1, the L operation is performed using the results xcex11,M+1(m), xcex10,M+1(m) of the A operation at k=M+1 and xcex2M+1(m) that has been stored in memory, and the decoded result uM+1 and likelihood L (uM+i) are calculated based upon the joint probabilities. Thereafter, and in similar fashion, the A operation is performed from k=M+2 to k=2M and the L operation is performed based upon the results of the A operation and the results of the B operation in memory. This ends the calculation of the decoded result uk and likelihood L (uk) from k=M+1 to k=2M.
Next, in similar fashion, (5) the B operation is performed from k=4M to 2M+1 and the backward probability xcex2k(m) found over k=3M to k=2M+1 of the second half is stored in memory. (6) Next, the A operation is performed at k=2M+1, the L operation is performed using the results xcex11,2M+1(m), xcex10,2M+1(m) of the A operation at k=2M+1 and xcex22M+1(m) that has been stored in memory, and the decoded result u2M+1 and likelihood L (u2M+i) are calculated based upon the joint probabilities. Thereafter, the A operation is performed from k=2M+2 to k=3M and the L operation is performed based upon the results of the A operation and the results of the B operation in memory. This ends the calculation of the decoded result uk and likelihood L (uk) from k=2M+1 to k=3M.
This is followed by performing similar operations. Finally, (7) the B operation is performed from k=N (=5M) to k=3M+1 and all backward probabilities xcex2k(m) found are stored in memory. (8) Next, the A operation is performed at k=3M+1, the L operation is performed using the results xcex11,3M+1(m), xcex10,3M+1(m) of the A operation at k=3M+1 and xcex23M +1(m) that has been stored in memory, and the decoded result u3M+1 and likelihood L (u3M+i) are calculated based upon the joint probabilities. Thereafter, the A operation is performed from k=3M+2 to k=N (=5M) and the L operation is performed based upon the results of the A operation and the results of the B operation in memory. This ends the calculation of the decoded result uk and likelihood L (uk) from k=3M+1 to k=N.
The third MAP decoding method is advantageous in that the memory for storage of the backward probabilities can be reduced to 2M. Moreover, the time needed to output the initial decoded result u1 and likelihood L (u1) can be curtailed.
With the third MAP decoding method, however, the backward probability xcex2k(m) is not calculated from k=N but is calculated from an intermediate point. As a consequence, the backward probability xcex2k(m) is not accurate and a problem that arises is a decline in the precision of MAP decoding.
Further, with the third MAP decoding method, the A calculation over M is performed after the B calculation over 2M, and therefore the result in the form of a time chart is as shown in FIG. 36(a). However, since this method renders the A operation intermittent, calculation takes time. Accordingly, by performing the first and second halves of the B operation simultaneously, as illustrated in FIG. 36(b), the A operation can be executed continuously, thereby raising operation speed. However, the problem with this method is that two B arithmetic circuits are required because the first and second halves of the B operation are executed simultaneously.
A further problem with the third MAP decoding method is that the calculation of the backward probability xcex2k(m) is repeated, i.e., performed twice, so that there is an overall increase in power consumption.
Accordingly, an object of the present invention is to cut down on memory and calculate backward probability xcex2k(m) accurately to raise the precision of MAP decoding.
Another object of the present invention is to arrange it so that a prescribed operation speed can be obtained without using two arithmetic circuits to calculate backward probability xcex2k(m).
Another object of the present invention is to make it possible to calculate backward probability xcex2k(m) accurately by calculating backward probability xcex2k(m) just one time, thereby providing an advantage in terms of power consumption.
In a first MAP decoding method, (1) backward probabilities are calculated in a reverse direction from an Nth backward probability to a first backward probability, an m1th backward probability to the first backward probability are saved, then first forward probability is calculated, a first decoded result is obtained using the first forward probability and the saved first backward probability, and second to m1th decoded results are obtained in similar fashion. (2) Thereafter, backward probabilities are calculated in the reverse direction from the Nth backward probability to an (m1+1)th backward probability, an m2th backward probability to the (m1+1)th backward probability are saved, (m1+1)th forward probability is calculated, an (m1+1)th decoded result is obtained using the (m1+1)th forward probability and the saved (m1+1)th backward probability, (m1+2)th to m2th decoded results are obtained in similar fashion and (3) (m2+1)th to Nth decoded results are subsequently obtained in similar fashion.
If this arrangement is adopted, a memory capacity of just rxc3x97m (number of states) is required to store the backward probabilities, where m1=r, m2=2 r, . . . holds. Moreover, since the backward probabilities are calculated from k=N at all times, backward probability xcex2k(m) is calculated accurately to make it possible to raise the precision of MAP decoding.
In another MAP decoding method, (1) backward probabilities are calculated in a reverse direction from an Nth backward probability to a first backward probability, an msth backward probability, m(sxe2x88x921)th backward probability, . . . , m2th backward probability are saved discretely, an m1th backward probability to the first backward probability are saved continuously, first forward probability is calculated, a first decoded result is obtained using the first forward probability and the saved first backward probability, and second to m1th decoded results are obtained in similar fashion. (2) Thereafter, backward probabilities up to an (m1+1)th backward probability are calculated and saved starting from the saved m2th backward probability, (m1+1)th forward probability is calculated, an (m1+1)th decoded result is obtained using the (m1+1)th forward probability and the saved (m1+1)th backward probability, (m1+2)th to m2th decoded results are obtained in similar fashion and (3) (m2+1)th to Nth decoded results are subsequently obtained in similar fashion.
If this arrangement is adopted, a memory capacity of just rxc3x97m (number of states) is required to store the backward probabilities, where m1=r, m2=2 r, . . . holds. Further, it is so arranged that backward probabilities are calculated in a reverse direction from an Nth backward probability to a first backward probability, the obtained backward probabilities are stored discretely and, if necessary, backward probabilities of the required number are calculated and utilized starting from one of the discretely stored backward probabilities. As a result, backward probability xcex2k(m) can be calculated accurately to make it possible to raise the precision of MAP decoding. Moreover, backward probabilities of the required number need not be obtained by calculating backward probabilities from k=N on as the occasion demands. Operation speed can be raised as a result. Further, a prescribed operation speed is obtained without using two arithmetic circuits to calculate backward probability xcex2k(m). Furthermore, backward probability xcex2k(m) need be calculated just one time, thereby providing an advantage in terms of power consumption.